package com.zhang.graph.undirectedgraph;

import javafx.scene.Parent;

import java.util.*;

/**
 * @author zhang
 * @time 2022/03/02 22:37:22
 */
public class WeightedGraph {
    private class Node {
        private String label;
        private List<Edge> edges = new ArrayList<>();
        private List<Edge> getEdges() {
            return this.edges;
        }

        public Node(String label) {
            this.label = label;
        }

        private void addEdge(Node to, int weight) {
            this.edges.add(new Edge(this, to, weight));

        }

        @Override
        public String toString() {
            return label;
        }
    }

    private class Edge {
        private Node from;
        private Node to;
        private int weight;

        public Edge(Node from, Node to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return from + "->" + to;
        }
    }

    private Map<String, Node> nodes = new HashMap<>();
    public void addNode(String label) {
        nodes.putIfAbsent(label, new Node(label));
    }

    public void addEdge(String from, String to, int weight) {
        Node fromNode = nodes.get(from);
        if (fromNode == null) {
            return;
        }
        Node toNode = nodes.get(to);
        if (toNode == null) {
            return;
        }
        fromNode.addEdge(toNode,weight);
        toNode.addEdge(fromNode,weight);
    }
    public void print() {
        for (Node node : nodes.values()) {
            List<Edge> edges = node.getEdges();
            if (!edges.isEmpty()) {
                System.out.println(node + "connnected to " + edges);
            }

        }
    }
    private class NodeEntry {
        private Node node;
        private int priority;

        public NodeEntry(Node node, int priority) {
            this.node = node;
            this.priority = priority;
        }

        @Override
        public String toString() {
            return "NodeEntry{" +
                    "node=" + node +
                    ", priority=" + priority +
                    '}';
        }
    }

    private class Path {
        private List<String> nodes = new ArrayList<>();

        public void addNode(String node) {
            nodes.add(node);
        }
        @Override
        public String toString() {
            return nodes.toString();
        }
    }

    public Path getShortestPath(String from,String to) {
        Node fromNode = nodes.get(from);
        Node toNode = nodes.get(to);
        //给距离表赋初始值 除了第一个节点是0 剩下的都是最大整数
        Map<Node,Integer> distances = new HashMap<>();
        for (Node node : nodes.values()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.replace(fromNode, 0);
        Map<Node, Node> preivous = new HashMap<>();
        Set<Node> visted = new HashSet<>();
        //给优先队列 传比较器
        PriorityQueue<NodeEntry> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.priority));
        queue.add(new NodeEntry(fromNode, 0));
        while (!queue.isEmpty()) {
            Node current = queue.remove().node;
            visted.add(current);

            for (Edge edge : current.getEdges()) {
                if (visted.contains(edge.to)) {
                    continue;
                }
                int newDistance = distances.get(current) + edge.weight;
                if (newDistance < distances.get(edge.to)) {
                    distances.replace(edge.to, newDistance);
                    preivous.put(edge.to,current);
                    queue.add(new NodeEntry(edge.to, newDistance));
                }
            }
        }
        return buildPath(preivous, toNode);
    }

    public Path buildPath(Map<Node,Node> previousNode, Node toNode) {
        Stack<Node> stack = new Stack<>();
        stack.push(toNode);
        Node preivous = previousNode.get(toNode);
        while (preivous != null) {
            stack.push(preivous);
            preivous = previousNode.get(preivous);
        }
        Path path = new Path();
        while (!stack.isEmpty()) {
            path.addNode(stack.pop().label);
        }
        return path;
    }

    public boolean hasCycle() {
        Set<Node> visited = new HashSet<>();
        for (Node node : nodes.values()) {
            if (!visited.contains(node) && hasCycle(node, null, visited)) {
                return true;
            }
        }
        return false;

    }

    private boolean hasCycle(Node node, Node parent, Set<Node> visited) {
        visited.add(node);
        for (Edge edge : node.getEdges()) {
            if (edge.to == parent) {
                continue;
            }
            if (visited.contains(edge.to) || hasCycle(edge.to, node, visited)) {
                return true;
            }
        }
        return false;
    }

    public boolean containsNode(String label) {
        return nodes.containsKey(label);
    }
    public WeightedGraph getMinimumSpingTree() {
        WeightedGraph tree = new WeightedGraph();
        PriorityQueue<Edge> edges = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

        Node startNode = nodes.values().iterator().next();
        edges.addAll(startNode.getEdges());
        tree.addNode(startNode.label);
        while (tree.nodes.size() < nodes.size()) {
            Edge minEdge = edges.remove();
            Node nextNode = minEdge.to;
            if (tree.containsNode(nextNode.label)) {
                continue;

            }
            tree.addNode(nextNode.label);
            tree.addEdge(minEdge.from.label, nextNode.label, minEdge.weight);
            for (Edge nedge : nextNode.getEdges()) {
                if (!tree.containsNode(nedge.to.label)) {
                    edges.add(nedge);
                }

            }
            System.out.println("666");

        }

        return tree;
    }

    public static void main(String[] args) {
        WeightedGraph wg = new WeightedGraph();
        //最短路径
//        wg.addNode("A");
//        wg.addNode("B");
//        wg.addNode("C");
//        wg.addNode("D");
//        wg.addNode("E");
//        wg.addEdge("A","B",3);
//        wg.addEdge("A","C",4);
//        wg.addEdge("A","D",2);
//        wg.addEdge("B","E",1);
//        wg.addEdge("B","D",6);
//        wg.addEdge("D","E",5);
//        wg.addEdge("D","C",1);
//        System.out.println(wg.getShortestPath("A", "E"));
// ----------------------------------------------------
        //最小生成树

        wg.addNode("A");
        wg.addNode("B");
        wg.addNode("C");
        wg.addNode("D");
        wg.addEdge("A","B",3);
        wg.addEdge("A","C",4);
        wg.addEdge("A","D",2);
        wg.addEdge("B","D",6);
        wg.addEdge("D","C",1);
        wg.getMinimumSpingTree().print();

    }

}
